Satellite communications experience unique challenges in signal transfer due to distance, imperfections of space electronics and atmospheric conditions. Whether satellites are exchanging signals with a ground device or another space-based device, there is a need to improve the reliability, speed and bandwidth of the communication link.
To increase throughput and efficiency, modern communication systems employ a variety of coding and modulation strategies, as represented in the block diagram of a satellite communication system 100 of FIG. 1. At a transmitter, information bits from bit source 102 are encoded by encoder 104 then interleaved by interleaver 104. Constellation mapper 108 then maps the bits into complex symbols before sending them to SRRC PSF (square root raised cosign pulse shaping filter) 110, digital to analog converter 112 and high power amplifier 114, which sends the symbols over communication channel 116. While traveling through the channel, the symbols in a data stream experience noise and other distortions including intersymbol interference (ISI) where one symbol interferes with neighboring symbols. The source of ISI can be either linear or non-linear.
At a receiver, thermal noise modeled as downlink AWGN (additive white Gaussian noise) 118 is added to the received signal in a summer 120 then sent to RF (radio frequency) Front-End 122. The signal is converted from analog back to digital in A/D 124 then passes through time synchronization block 126 and carrier & clock recovery block 128 as would be understood by one of ordinary skill in the art. The receiver than send the signal through FE-FIR MF (front-end finite impulse response matched filter) 130 before equalizer 132 uses one of several methods, for example, maximum likelihood sequence estimation (MLSE) or reduced sequence state estimation (RSSE), to reduce intersymbol interference to recover the complex symbols before they are de-interleaved in block 134 and decoded in block 136 and sent on to the receiving device, represented as bit sink 140.
An improvement to this system features turbo equalization, which adds a feedback path including interleaver 138 from decoder 136 back to the equalizer 132 of FIG. 1. In order to perform turbo equalization, one must be able to compute the soft-information for each coded bit within each symbol. “Soft information” is a commonly used term in the industry and refers to the Log-Likelihood Ratios (LLRs). LLRs are essentially a statement of how likely a given coded information bit was transmitted given the channel observations and other a priori information. To this end, BCJR is an optimal algorithm to determine a-posteriori probabilities (APPs) of each coded information bit transmitted over an ISI channel given the channel observations. The algorithm operates on a trellis structure in a memory defined by the length of channel memory and modulation order.
Retrieving LLRs from a data signal using the BCJR algorithm requires calculating 4 important metrics. The forward recursion metric, ads), is proportional to the probability of being in state s at time i given the channel observations up to time i. The backward recursion metric, βi(s), is proportional to the probability of the channel observations after time i given being in state s at time i. The transition or branch metric, γi(s, s′), is proportional to the probability of being in state s′ at time i and the channel observation at time i, given having been in state s at time i−1. Lastly, the total probability metric, σi(s, s′), is proportional to the probability of transitioning from state s to state s′ at time i−1, from which we compute the APP of each coded information bit. The forward and backward metrics and the total probability metrics are calculated using the following recursion equations:αi(s)=Σs′εSαi−1(s′)·γi(s′,s)  [1]βi(s)=Σs′εSβi+1(s′)·γi+1(s,s′)  [2]σi(s′,s)=αi−1(s′)·γi(s′,s)·βi(s)  [3]
The BCJR algorithm recursively computes these quantities by passing over the trellis from time 0 to time L and computing the forward recursion metrics where L is the length of the trellis, then from time L to time 0 computing the backward recursion metrics, and then finally from time 0 to time L computing the total probability metrics, from which the coded bit-wise APPs are calculated.
From a computational complexity standpoint the BCJR is very intensive because it must store the structure of a large trellis, or data structure, in memory including various metrics for each state and transition in the trellis, and must traverse the trellis 3 times in order to calculate the end result. The trellis data structure is generally represented as a grid of states, with columns representing time and rows representing the complexity of the system (or vice versa), i.e. the length of ISI channel memory and the modulation order. The channel memory is a result of the interference between neighboring symbols as they are being communicated through the channel.
In addition to being computationally intensive, the BCJR algorithm is time intensive because it can't begin executing until the entire data structure is populated.
In the case of intersymbol interference (ISI) communication channels the number of states in the trellis grows exponentially with the length of channel memory and modulation order. This in turn causes the complexity of the MLSE BCJR algorithm quickly to become intractable for many practical applications.
There have been efforts to improve MLSE BCJR from both a computational complexity and memory complexity standpoint. A modification to the MLSE BCJR algorithm is known as the sliding window BCJR (SW-BCJR).
The SW-BCJR algorithm allows for use of parallelization for the classic MLSE BCJR in a pipelined environment, in other words, with a continuous data stream. The windows in SW-BCJR allow execution of the algorithm to occur on a continuous basis, i.e. before the entire data structure is populated. There are two functioning parameters: the window size, w, and the overlap region, l. The trellis is divided into windows of length w time epochs such that each window has a “forward overlap region” of l time epochs, followed by w−2l time epochs, followed by a “backward overlap region” of l time epochs. Consecutive windows overlap one another for 2l epochs so that the forward overlap region of one window shares no common time epochs with the backward overlap region of its neighbor. Thus there are
  ⌈      L          w      -              2        ⁢                                  ⁢        l              ⌉windows, and each standard window contains w−2l distinct (non-overlapping) time epochs. The two non-standard windows are the first, which contains w−l distinct epochs, and the last window, which contains (L mod w−2l)−l distinct epochs.
For a given window the forward recursion metrics, α, and the backward recursion metrics, β, are initialized uniformly. The standard MLSE BCJR algorithm is carried out on each window independently under these conditions. Due to the uniform initialization, the execution of the MLSE BCJR algorithm in each window is independent of its execution in every other window. This uniform initialization creates a sub-optimality of the MLSE BCJR algorithm, however, the forward and backward recursion metrics converge to the values produced by the full MLSE BCJR (e.g. being memory and time intensive) within a small enough error that the overall bit error rate (BER) performance is unaffected. The final total probabilities are computed only on the distinct time epochs of each window, throwing out the unconverged metrics of the overlap regions. The parameter l is chosen to be large enough such that this convergence is tight enough as to not affect the final performance.
While providing reduced memory requirements and the opportunity for faster operation, the SW-BCJR, which based on MLSE trellis construction, does not degrade BER performance in uncoded or coded communications regimes. For large enough window size and overlap region, the degradation in performance is negligible. Typically, the BER between the SW-BCJR and the full BCJR is 0 (within numerical precision) for an overlap region of 10 and window size of 100 in QPSK, 8PSK, 16APSK and 32APSK modulations.
Another improvement to the classic MLSE BCJR algorithm is the reduced state sequence estimation (RSSE) for ISI channels which provides a method for reducing the number of states needed in the trellis description. This in turn reduces the complexity of any algorithms which run on the trellis.
For example, for a channel with memory length K, the full-complexity trellis for MLSE has MK states, where each state at time n corresponds to the K most recent symbols transmitted, [xn−1, xn−2, . . . , xn−K]. In RSSE, the symbol constellation set is partitioned K times, such that each partitioning, Ωi, has Ji subsets. This partitioning requires that J1≧J2≧ . . . ≧JK and Ωi is a further partitioning of Ωi+1. If these two conditions are met then there is a subset state at time n which depends on the subsets of the K most recent symbols, [an−1(1), an−2(2), . . . , an−K(K)]. These subset states determine a proper trellis. Because each an−1 must be a subset from Ωi (which has order Ji) there are J1. J2 . . . JK states in this new reduced trellis. This can be a dramatic reduction of number of states in the complexity of the trellis.
Trellis based decoding algorithms, such as the Viterbi algorithm or BCJR, are implemented by recursively traversing the trellis and making decisions and calculations about each transition based on previous calculations. On a reduced trellis, such as one resulting from RSSE, the same decisions cannot be made due to the parallel transitions. Thus, to implement BCJR on a reduced trellis, the system must maintain a path history of the last K symbols preceding each state. This is because, in the case of RSSE BCJR, calculation of forward metrics at time n, αn(i) takes the path history of each state into account when calculating the branch metrics, and calculates a branch metric for each symbol in the parallel transition.
Thus, a need exists for an improved satellite communications system using an algorithm that combines parallelism with a reduced state that requires path history. In other words, a data transfer processing technique that is both being memory efficient (e.g. RSSE BCJR uses reduced number of states in trellis construction) and time efficient (e.g. ability to parallel processing each independent SW within reduced state trellis).